1. Field of Use
The present invention relates generally to computer graphics, and more specifically, to a system and method for determining which pixels to render as part of a triangle in order to rasterize polygons.
2. Related Art
Raster displays are commonly used in computer graphics systems. These displays store graphics images as a matrix of picture elements or "pixels" (also referred to as PELs) with data representing each pixel being stored in a display buffer. This data specifies the display attributes for each pixel on the screen such as the intensity and color of the pixel. An entire image is read from the display buffer and painted on the screen by sequentially scanning out horizontal rows of pixel data or "scan lines," and using this data to control one or more electron beams (of course other display technologies can be used such as LCDs). This process of scanning pixel data out of the display buffer row-by-row is repeated every refresh cycle.
Raster display systems commonly use polygons as basic building blocks or "primitives" for drawing more complex images. Triangles are a common basic primitive for polygon drawing systems, since a triangle is the simplest polygon and more complex polygons can always be represented as sets of triangles. The process of drawing triangles and other geometric primitives on the screen is known as "rasterization." The rasterization of polygons is a problem fundamental to both two-dimensional and three-dimensional graphics systems. Most techniques that apply to the rasterization of triangles can be generalized for a polygon with any number of sides.
An important part of rasterization involves determining which pixels fall within a given triangle. Rasterization systems generally step from pixel to pixel and determine whether or not to "render" (i.e., draw into a frame buffer or pixel nap) each pixel as part of the triangle. This, in turn, determines how to set the data in the display buffer representing each pixel. Various traversal algorithms have been developed for moving from pixel to pixel in a way such that all pixels within the triangle are covered.
Rasterization systems sometimes represent a triangle as a set of three edge-functions. An edge function is a linear equation representing a straight line, which serves to subdivide a two-dimensional plane. Edge functions classify each point within the plane as falling into one of three regions: the region to the "left" of the line, the region to the "right" of the line, or the region representing the line itself. The type of edge function which will be discussed has the property that points to the "left" of the line have a value greater than zero, points to the "right" have a value less than zero, and points exactly on the line have a value of zero (this can be seen in FIG. 1). Applied to rasterization systems, the two-dimensional plane is represented by the graphics screen, points are represented by individual pixels, and the edge function serves to subdivide the graphics screen.
Triangles are created by the union of three edges, each of which are specified by edge functions. It is possible to define more complex polygons by using Boolean combinations of more than three edges. Since the rasterization of triangles involves determining which pixels to render, a tie-breaker rule is generally applied to pixels that lie exactly on any of the edges to determine whether the pixels are to be considered interior or exterior to the triangle.
Each pixel has associated with it a set of edge variables, (e.sub.0, e.sub.1, e.sub.2), which represent the signed distance between the pixel and the three respective edges, as shown in FIG. 2. The value of each edge variable is determined for a given triangle by evaluating the three edge functions, f.sub.0 (x,y),f.sub.1 (x,y) and f.sub.2 (x,y) for the pixel location. Edge variables can have fractional values, since an edge may fall between two adjacent pixels. It is convenient, therefore, to represent edge variables in fixed point 2's complement integer format. Note that it can be determined whether or not a pixel falls within a triangle by looking at the signs of e.sub.0, e.sub.1 and e.sub.2, if it is known whether each edge is a "right" edge or a "left" edge of the triangle. Note that the signs of the edges can be reversed if desired.
In determining which pixels to render within a triangle, typical rasterization systems compute the values of the edge variables, (e.sub.0, e.sub.1, e.sub.2), for a given set of three edge functions and a given pixel position, and then use a set of increment values (.DELTA.e.sub.left,.DELTA.e.sub.right, etc.) to determine the edge variable values for adjacent pixels. The rasterization system traverses the triangle, adding the increment values to the current values as a traversal algorithm steps from pixel to pixel. A pixel that is within the triangle bounds according to the pixel's three edge variable values (and any tie-breaker rules) will be rendered.
Systems having simple hardware generally perform these computations separately for each pixel while more complex systems having more arithmetic units may compute the values for multiple pixels simultaneously. Although parallel evaluation of the edge variables for multiple pixels results in faster rasterization, the process remains limited by the need to separately determine the edge variables for every traversed pixel.
An examination of an edge function which can be used to rasterize triangles, and of various algorithms for traversing the triangle, will provide a better understanding of the process described above. A detailed description of the use of edge functions and traversal algorithms can be found in "A Parallel Algorithm for Polygon Rasterization," Pineda, J., Computer Graphics 22(4): 17-20 (1988), which is incorporated by reference herein. Portions of the Pineda reference have been substantially reproduced below for the convenience of the reader.
Consider, as shown in FIG. 3, a vector defined by two points: (X,Y) and (X+dX,Y+dY), and the line that passes through both points. As noted above, this vector and line can be used to divide the two dimensional space into three regions: all points to the "left" of, to the "right" of, and exactly on the line.
The edge f(x,y) can be defined as: EQU f(x,y)=(x-X)dY-(y-Y)dX
This function has the useful property that its value is related to the position of the point (x,y) relative to the edge defined by the points (X,Y) and (X+dX, Y+dY): EQU f(x,y)&gt;0 if (x,y) is to the "right" side EQU f(x,y)=0 if (x,y) is exactly on the line EQU f(x,y)&lt;0 if (x,y) is to the "left" side
To convince oneself that this is true, those skilled in the art will recognize that the formula given for f(x,y) is the same as the formula for the magnitude of the cross product between the vector from (X,Y) to (X+dX, Y+dY), and the vector from (X,Y) to (x,y). By the well known property of cross products, the magnitude is zero if the vectors are collinear, and changes sign as the vectors cross from one side to the other.
This function is commonly used by existing rasterization systems, since it can be computed incrementally by simple addition: EQU f(x+1,y)=f(x,y)+dY EQU f(x,y+1)=f(x,y)+dX
The edge function is related to the error value or "draw control variable" (DCV) in Bresenham line drawing algorithms described in "Algorithm for Computer Control of a Digital Plotter," Bresenham, J., IBM Systems Journal 4(1):25-30 (1965). The difference is that Bresenham line drawing algorithms maintain the DCV value only for pixels within 1/2 pixel of the line, while f(x,y) is defined for all pixels on the plane. In addition, the value of the DCV at a given point differs from f(x,y) by a constant offset. In any case, the reason that both algorithms work is fundamentally the same.
This same property of f(x,y) is used by the graphics system described in "PIXEL-PLANES" graphics system, described in Fuchs, et al., VLSI Design (3rd Quarter):20-28 (1981), where this function is computed in parallel for all pixels in the frame buffer by a multiplier tree.
A variety of different traversal algorithms are presently used by different rasterization systems in the rendering process. Any algorithm guaranteed to cover all of the pixels within the triangle can be used. FIG. 4 shows two simple implementations of traversal algorithms. Traversing the bounding box is perhaps the simplest strategy, as shown in FIG. 4(a), but generally not the most efficient. A smarter algorithm, shown in FIG. 4(b), would advance to the next traversal line when it "walks" off the edge of a triangle.
One complication of the smarter algorithm is that when it advances to the next line, it may advance to a point inside the triangle. In that case, the algorithm must search for the outside of the edge before it begins the next scan line. An example of this problem is shown on the top right hand edge of the triangle in FIG. 5.
An implementation of an even smarter algorithm is shown in FIG. 6. It proceeds down from the starting point, working its way outward from a center line. The advantage of this algorithm over the simpler algorithm is that it never has to search for an edge, then double back. The tradeoff is that the interpolator state for the center line must be saved while traversing the outer points, since the interpolators must be restarted back at the center line. Notice that at the bottom, the "center" line shifts over if it ends up exterior to the triangle.
There are a number of different ways to traverse the pixels in the triangle. The efficiency of each method depends upon the particular triangle being rendered. Many systems organize pixels in the memory in rectangular blocks. Some of these systems then cache these blocks in a fast memory, similar to the way a CPU caches data and instructions. When used in conjunction with an appropriate traversal algorithm, this organization can improve performance by keeping memory accesses to a minimum.
Regardless of the amount of hardware available or the method of traversing the pixels within the triangle, at least three addition operations must be performed per pixel when using the pixel-by-pixel method described above. These three additions correspond to the three increment values which must be added to the values of the edge variables, e.sub.0, e.sub.1 and e.sub.2, to determine the respective values for an adjacent pixel, as discussed above. Thus, under present rasterization techniques, efficiency is limited by the number of calculations per pixel required to determine whether or not the pixel falls within the triangle. This limited efficiency translates into slower graphics display systems. A method for rendering triangles which reduces the number of calculations required per pixel is therefore required.